def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    # 复制数据到辅助数组
    L = [arr[l + i] for i in range(n1)]
    R = [arr[m + 1 + j] for j in range(n2)]

    i = 0  # 初始化左边子数组的索引
    j = 0  # 初始化右边子数组的索引
    k = l  # 初始化合并子数组的索引

    # 合并两个子数组回到原数组
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

def merge_sort(arr, l, r):
    if l < r:
        m = l + (r - l) // 2

        merge_sort(arr, l, m)
        merge_sort(arr, m + 1, r)

        merge(arr, l, m, r)



# 测试示例
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
merge_sort(arr,0,len(arr)-1)
print(arr)